#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void PrintArray(vector<int>& v, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}

int GetMid(vector<int>& v, int left, int right)
{
    int mid = (left + right) / 2;
    if (v[left] < v[mid])
    {
        if (v[mid] < v[right])
        {
            return mid;
        }
        else if (v[left] > v[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else //v[left] > v[mid]
    {
        if (v[mid] > v[right])
        {
            return mid;
        }
        else if (v[left] < v[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

int QuickSort2(vector<int>& v, int begin, int end)
{
    int midi = GetMid(v, begin, end);
    ::swap(v[begin], v[midi]);
    int key = v[begin];
    int hole = begin;
    while (begin < end)
    {
        while (begin < end && v[end] >= key)
        {
            end--;
        }

        v[hole] = v[end];
        hole = end;

        while (begin < end && v[begin] <= key)
        {
            begin++;
        }

        v[hole] = v[begin];
        hole = begin;
    }

    v[hole] = key;

    return hole;
}

void QuickSortNonR(vector<int>& v, int begin, int end)
{
    stack<int> st;
    st.push(begin);
    st.push(end);

    while (!st.empty())
    {
        int right = st.top();
        st.pop();
        int left = st.top();
        st.pop();

        int keyi = QuickSort2(v, left,right);

        if (keyi + 1 < right)
        {
            st.push(keyi + 1);
            st.push(right);
        }

        if (left < keyi - 1)
        {
            st.push(left);
            st.push(keyi - 1);
        }
    }
}

void TestQuickSortNonR()
{
    //int a[] = { 6, 1, 6, 7, 6, 6, 4, 5, 6, 8 };
    //int a[] = { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };
    vector<int> v = { 6, 1, 6, 7, 6, 6, 4, 5, 6, 8 };
    QuickSortNonR(v,0,v.size()-1);
    //QuickSortNonR(a, 0, sizeof(a) / sizeof(int)-1);
    PrintArray(v,v.size());
}

int main()
{
    // TestInsertSort();
    // TestShellSort();
    // TestBubbleSort();
    // TestHeapSort();
    // TestSelectSort();
    TestQuickSortNonR();

    return 0;
}
